package Graph.graphWithNoweight.bfs;

import java.util.HashSet;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/9 14:43
 * @Version 1.0
 *
 * 计算岛屿最大面积，，也就是给你一个图，计算最大的联通分量。
 */
public class leetCode0695 {
    private int R,C;
    private int[][] grid;

    //这个4个位置分别 代表左上右下
    private int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
    private HashSet<Integer>[] G;
    private boolean[] visited;

    public int maxAreaOfLand(int[][] grid){
        if(grid == null){
            return 0;
        }
        R = grid.length;
        C = grid[0].length;
        if(R ==0||C==0){
            return 0;
        }
        this.grid = grid;
        //注意这里的G 是 hashSet 的 也就是R*C个数
        G = constructGraph();
        int res = 0;
        visited = new boolean[G.length];
        for(int v=0;v<G.length;v++){
            int x = v/C;
            int y = v%C;
            if(!visited[v] && grid[x][y] ==1){
                res = Math.max(res,dfs(v));
            }
        }

        return res;
    }

    private int dfs(int v) {
        visited[v] = true;
        int res = 1;
        for(int w:G[v]){
            if(!visited[w]){
                res += dfs(w);
            }
        }
        return res;
    }

    private HashSet<Integer>[] constructGraph() {
        //虽然已经有了 grid[][] ，，但是用HashSet 来表示每个点可以走路
        HashSet<Integer>[] g = new HashSet[R*C];
        for(int i=0;i<g.length;i++){
            g[i] = new HashSet<>();
        }
        for(int v=0;v<g.length;v++){
            int x = v/C;
            int y = v%C;
            if(grid[x][y] == 1){
                for(int d=0;d<4;d++){
                    int nextx = x+dirs[d][0];
                    int nexty = x+dirs[d][1];
                    //这里相当于够着v 的周围变量  ，，相当于G.adj()
                    if(inArea(nextx,nexty) && grid[nextx][nexty] == 1){
                        int next = nextx * C +nexty;
                        g[v].add(next);
                        g[next].add(v);
                    }
                }
            }
        }
        return g;
    }

    private boolean inArea(int nextx, int nexty) {
        return nextx>=0 && nextx<R || nexty>=0 && nexty<C;
    }
}
